package leetcode_300;

/**
 *@author 周杨
 *MinimumSizeSubarraySum_209 找连续最小数组  大于或者等于目标数
 *describe:哨兵标记区间左  记录当前最小 AC 59%
 *2018年6月14日 上午11:06:05
 */
public class MinimumSizeSubarraySum_209 {

	public static void main(String[] args) {
		MinimumSizeSubarraySum_209 test=new MinimumSizeSubarraySum_209();
		/*System.out.println(test.minSubArrayLen1(7, new int[] {2,3,1,2}));
		System.out.println(test.minSubArrayLen1(11, new int[] {1,2,3,4,5}));*/
		System.out.println(test.minSubArrayLen(15, new int[] {5,1,3,5,10,7,4,9,2,8}));
	}
	
	/**
	 * describe:题目没看清楚 这是加起来=s的解法
	 * 2018年6月14日 上午10:49:28
	 */
	public int minSubArrayLen1(int s, int[] nums) {
        int res=Integer.MAX_VALUE;
        int con=0,pre=0;
        for(int i=0;i<nums.length;++i) {
        	con=con+nums[i];//先加
        	if(con==s) {
        		res=i-pre+1;
        		if(res==1)
        			return 1;
        		else {
        			con=con-nums[pre]-nums[pre+1];
        			pre+=2;//压缩可能有结果的区域
        		}
        	}
        	else if(con>s) {
        		while(pre<=i) {//缩小size
        			con=con-nums[pre];
        			++pre;
        			if(con==s) {
        				res=i-pre+1;
        				if(res==1)
                			return 1;
                		else {
                			con=con-nums[pre]-nums[pre+1];
                			pre+=2;//压缩可能有结果的区域
                			break;
                		}
        			}
        			else if(con>s) {
        				;
        			}
        			else
        				break;
        		}
        	}
        	else {//小
        		if(i-pre+1==res) {//快要超过边界
        			++pre;
        			con=con-nums[pre];
        		}
        		else {
        			
        		}
        	}
        }
        return res==Integer.MAX_VALUE?0:res;
    }
	
	
	public int minSubArrayLen(int s, int[] nums) {
		int res=Integer.MAX_VALUE;
		int con=0,pre=0;
		for(int i=0;i<nums.length;++i) {
			con+=nums[i];
			if(con<s) {
				if(i-pre+1==res) {
					con-=nums[pre];
					++pre;
				}
			}
			else {//大于或者等于
				res=i-pre+1;
				if(res==1)
					return 1;
				else {
					while(pre<=i) {
						con-=nums[pre];
						++pre;
						if(con>=s) {
							res--;
						}
						else
							break;
					}
				}
			}
		}
		return res==Integer.MAX_VALUE?0:res;
	}

}
